package com.com.datastructures.sort;

/**
 * Created with IntelliJ IDEA.
 * User: Ngo Lap Thanh
 * Date: 26/05/14
 * Time: 9:32 AM
 * To change this template use File | Settings | File Templates.
 */
public class QSearch {
   static public int data[] = {2,4,6,8,3,1,28,0,22}; // 0 to 8
    //public int data[] = {8,7,6,5,44,3,2,1,0};   //0 to 8
   // static public int data[] = {4,3,2,1};   // 0 to 3
   //public  static int data[] = {4,3,2,1,0,1,2,3,4,5,44,55,2,1,7,6,5,3,2,8,6,34,43};   // 0 to 22
   //public  static int data[] = {5,5,5,5};   // 0 to 3

    public int partitioning(int start, int end, int pivot){

        int leftPtr = start - 1;
        int rightPtr = end + 1;

        while(true){

            while( (leftPtr < end) && (data[++leftPtr] < pivot) ){
                //leftPtr++;
            }

            while( (rightPtr > start) &&  (data[--rightPtr] > pivot) ){
                //rightPtr--;
            }

            if(leftPtr >= rightPtr){
                System.out.print("\n leftPtr: "+leftPtr);
                System.out.print("\n rightPtr: "+rightPtr);
                //break;
                return leftPtr;

            }

            swap(leftPtr, rightPtr);
        }
    }

    public void partitioning2(int start, int end, int pivot){

        int leftPtr = start - 1;
        int rightPtr = end + 1;

        while(true){

            while( (leftPtr < end) && (data[++leftPtr] < pivot) );

            while( (rightPtr > start) &&  (data[--rightPtr] > pivot) );

            if(leftPtr >= rightPtr){
                break;
            }

            swap(leftPtr, rightPtr);
        }
    }

    public int pivotSelection(int start , int end) {

        return (start+end)/2;
    }

    public void sort(int start, int end){
        if(start>=end) return;
        int pivot = pivotSelection(start, end);
        System.out.println("\n pivot at:   "+pivot +"  is " +data[pivot] );
        int indexOfPivot = partitioning(start, end, data[pivot]);
        System.out.println("\n index of pivot :   "+indexOfPivot +"  has " +data[indexOfPivot] );
        sort(start, indexOfPivot-1);
        sort(indexOfPivot+1, end);
    }

    public void display(){
        System.out.print("\n Data: ");
        for(int item : data){
            System.out.print(item +", ");
        }
    }

    public void swap(int a, int b){
        int temp  = data[a];
        data[a]=data[b];
        data[b]=temp;
        System.out.print("\n swap "+temp + ", " + data[a] );
    }

    public static void main(String args[]){
        QSearch s = new QSearch();
        s.display();

        s.partitioning(0,data.length-1,22);

        //s.sort(0,data.length-1);

        s.display();

    }
}